package com.honeywen.mymvc.leetcode;


/**
 * 5. 最长回文子串
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 *
 * @author wangwei
 * @date 2019/8/6
 */
public class LongestPalindrome {

    public static String longestPalindrome(String s) {

        int lenth = s.length();
        int max = 0;
        String result = "";
        for (int i = 0; i < lenth; i++) {
            for (int j = i; j < lenth; j++) {
                String subString = s.substring(i, j + 1);
                boolean is_palindrom = isPalindrome(subString);
                if (is_palindrom) {
                    if (subString.length() >= max) {
                        result = subString;
                    }
                    max = Math.max(max, subString.length());

                }
            }

        }
        return result;

    }

    private static boolean isPalindrome(String subString) {
        boolean is_palindrom = true;
        int length = subString.length();
        for (int i = 0; i < length; i++) {
            char si = subString.charAt(i);
            char sj = subString.charAt(length - i - 1);
            if (si != sj) {
                return false;
            }
        }
        return is_palindrom;

    }



    public static String longestPalindrome5(String s) {

        if (s == null || s.length() < 2) {
            return s;
        }

        // 对称，和顶点
        int max = 0;
        int left = 0;
        int right = 0;
        for (int i = 0; i < s.length(); i++) {
            // 顶点
            int a = i - 1;
            int b = i + 1;

            int m = 1;
            while (a > -1 && b < s.length() && s.charAt(a) == s.charAt(b)) {

                m += 2;

                a--;
                b++;

            }

            if (m > max) {
                max = m;
                left = a + 1;
                right = b - 1;
            }

            // 对称
            a = i;
            b = i +1;
            m = 0;
            while (a > -1 && b < s.length() && s.charAt(a) == s.charAt(b)) {

                m += 2;
                a--;
                b++;
            }

            if (m > max) {
                max = m;
                left = a + 1;
                right = b - 1;
            }


        }


        return s.substring(left, right + 1);

    }


    public static void main(String[] args) {

//        System.out.println(longestPalindrome("babad"));
        System.out.println(longestPalindrome5("babad"));
//        System.out.println(longestPalindrome("babad"));
//        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome5("cbbd"));
//        System.out.println(longestPalindrome("cbbd"));
        System.out.println(longestPalindrome5("ccc"));
//        System.out.println(longestPalindrome("ccc"));
        System.out.println(longestPalindrome5("cccc"));
//        System.out.println(longestPalindrome("cccc"));

//        System.out.println(longestPalindrome2("abc"));

        String s = "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc";

//        System.out.println(longestPalindrome5(s));
//        System.out.println(longestPalindrome(s));
    }
}
